package offer;

public class offer_0013 {
    public int movingCount(int m, int n, int k) {
        int[][] dp=new int[m][n];
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(sum(i,j)>k){
                    dp[i][j]=1;
                }
            }
        }
        int[][] used=new int[m][n];
        int[] result=new int[1];
        num(dp,used,result,0,0,m,n);
        return result[0];
    }
    public int sum(int i,int j){
        int sum=0;
        while(i>0){
            sum+=i%10;
            i/=10;
        }
        while(j>0){
            sum+=j%10;
            j/=10;
        }
        return sum;
    }
    public void num(int[][] dp,int[][] used,int[] result,int i,int j,int m,int n){
        if(i<m&&i>=0&&j<n&&j>=0&&used[i][j]==0&&dp[i][j]==0){
            result[0]+=1;
            used[i][j]=1;
            num(dp,used,result,i-1,j,m,n);
            num(dp,used,result,i,j-1,m,n);
            num(dp,used,result,i+1,j,m,n);
            num(dp,used,result,i,j+1,m,n);
        }
    }
}
